package com.hanxiaozhang.recursion.violentrecursion;

/**
 * 〈一句话功能简述〉<br>
 * 〈给定一个整型数组arr，代表数值不同的纸牌排成一条线，
 * 玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，
 * 但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。
 * 请返回最后获胜者的分数〉
 *
 * @author hanxinghua
 * @create 2021/10/13
 * @since 1.0.0
 */
public class CardsInLine {


    public static void main(String[] args) {
       // int[] arr = {1, 9, 1};
        int[] arr = {1, 7, 9,100,101};
        System.out.println(win1(arr));
        System.out.println(win2(arr));

    }

    /**
     * 方法1
     *
     * @param arr
     * @return
     */
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 玩家一：0 ~ arr.length - 1 先手
        // 玩家二：0 ~ arr.length - 1 后手
        // 比较玩家一与玩家二
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    /**
     * 先手拿牌函数
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int f(int[] arr, int L, int R) {
        // L = R，证明数组只剩下一张牌了，直接返回这张牌
        if (L == R) {
            return arr[L];
        }
        // 情况一：拿走左侧牌 + L+1 ~ R 位置后手拿牌
        // 情况二：拿走右侧牌 + L ~ R-1 位置后手拿牌
        // 比较两种情况，选最好
        return Math.max(arr[L] + s(arr, L + 1, R),
                arr[R] + s(arr, L, R - 1));
    }

    /**
     * 后手拿牌函数
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int s(int[] arr, int L, int R) {
        // L = R，证明数组只剩下一张牌了，先手已经拿走这张牌，所以没有牌可以拿
        if (L == R) {
            return 0;
        }
        // 情况一：L+1 ~ R 位置先手拿牌
        // 情况二：L ~ R -1 位置先手拿牌
        // 比较两种情况，选最小
        return Math.min(
                f(arr, L + 1, R),
                f(arr, L, R - 1));
    }

    /**
     * 根据win1的暴力递归改动态规划
     *
     * @param arr
     * @return
     */
    public static int dpWays(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] f = new int[N][N];
        int[][] s = new int[N][N];
        // 构造f对角线的值
        for (int i = 0; i < N; i++) {
            f[i][i] = arr[i];
        }
        // s对角线默认初始化就是0
        for (int i = 1; i < N; i++) {
            int L = 0;
            int R = i;
            while (L < N && R < N) {
                f[L][R] = Math.max(arr[L] + s[L + 1][R], arr[R] + s[L][R - 1]);
                s[L][R] = Math.min(f[L + 1][R], f[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(f[0][N - 1], s[0][N - 1]);
    }


    /**
     * 动态规划
     *
     * @param arr
     * @return
     */
    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int R = 0; R < arr.length; R++) {
            f[R][R] = arr[R];
            for (int L = R - 1; L >= 0; L--) {
                f[L][R] = Math.max(arr[L] + s[L + 1][R], arr[R] + s[L][R - 1]);
                s[L][R] = Math.min(f[L + 1][R], f[L][R - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }

}
